/*
 * @lc app=leetcode.cn id=77 lang=cpp
 *
 * [77] 组合
 *
 * https://leetcode-cn.com/problems/combinations/description/
 *
 * algorithms
 * Medium (77.05%)
 * Likes:    962
 * Dislikes: 0
 * Total Accepted:    339K
 * Total Submissions: 439.9K
 * Testcase Example:  '4\n2'
 *
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * 
 * 你可以按 任何顺序 返回答案。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：n = 4, k = 2
 * 输出：
 * [
 * ⁠ [2,4],
 * ⁠ [3,4],
 * ⁠ [2,3],
 * ⁠ [1,2],
 * ⁠ [1,3],
 * ⁠ [1,4],
 * ]
 * 
 * 示例 2：
 * 
 * 
 * 输入：n = 1, k = 1
 * 输出：[[1]]
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 
 * 1 
 * 
 * 
 */

// @lc code=start
class Solution {
private:
//     vector<int> path;
//     vector<vector<int>> res;
//     void backtracking(int n, int k, int startIndex) {
//         if(path.size() == k) {
//             res.push_back(path);
//             return;
//         }

//         // for(int i = startIndex; i <= n; i++) { //普通做法
//         for(int i = startIndex; i <= n - (k - path.size()) + 1; i++) { //剪枝优化
//             /*
//                 优化原理
//                 path.size() ： 已经找的个数
//                 k-path.size() ：还需找的个数
//                 [n, k]的数组长度起码应该是k-path.size()才有继续搜索的可能， 
//                 那么就有 n-x+1 = k-path.size()  
//                 解方程得 x = n+1 - (k-path.size()),
//                 而且这个x是可以作为起点往下搜的 
//                 也就是for(i = s; i<=x; i++) 这里的x是可以取到的
//             */
//             path.push_back(i);
//             // 下一轮儿的backtracking的startIndex确实该加1，
//             // 但是backtracing完事儿之后，i应该立即减一
//             // 等待下一轮儿循环的 i自动加1 
//             backtracking(n, k, i+1); //这里的i+1而不是i++；撤销处理后的i，所以不是i++,或者++i
//             path.pop_back(); // 回溯，撤销处理节点
//         }
//     }
// public:
//     vector<vector<int>> combine(int n, int k) {
//         path.clear();
//         res.clear();
//         backtracking(n, k, 1);
//         return res;
    // }
private:
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(int n, int k, int startIndex) {
        if(path.size() == k) {
            res.push_back(path);
            return;
        }
        for(int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            path.push_back(i);
            backtracking(n, k, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        path.clear();
        res.clear();
        backtracking(n, k , 1);
        return res;
    }
};
// @lc code=end

